package LeetCode.interview;

import LeetCode.interview._021_Merge_Two_Sorted_Lists.ListNode;
import util.LogUtils;

/*
 * 
原题

　　Given two binary trees, write a function to check if they are equal or not. 
　　Two binary trees are considered equal if they are structurally identical and the nodes have the same value. 

题目大意

　　给定两个二叉树，判断这两棵树是否相等。 
　　仅当两棵树的结构相同，结点值都相等时都会相等。 

解题思路

　　使用递归进行求解，先判断当前结点值是否相等，如果相等就再比较其左右子树，只有当所有的结点都相等才相等。 
 * @Date 2017-09-13 15：36
 */
public class _100_Same_Tree {
	
	public class TreeNode {
	    int val;
	    TreeNode left;
	    TreeNode right;
	    TreeNode(int x) { val = x; }
	    public TreeNode(int x, TreeNode l, TreeNode r) {val = x; left = l; right = r;}
	}
	
	public boolean isSameTree(TreeNode p, TreeNode q) {
		/**
		 * 判断结构是否相同  假如两棵树结构完全相同，最后会返回true
		 */
		if (p==null && q==null)	return true;				
		if (p==null && q!=null)	return false;
		if (p!=null && q==null)	return false;
		return (p.val==q.val) && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
	}
    
	private TreeNode newTree1() {
		return new TreeNode(1, 
					new TreeNode(2, 
							new TreeNode(4), new TreeNode(5)
					), 
					new TreeNode(3, 
							new TreeNode(6), new TreeNode(7)
					)
				);
	}
	
	private TreeNode newTree2() {
		return new TreeNode(1, 
				new TreeNode(2, 
						new TreeNode(4), new TreeNode(5)
				), 
				new TreeNode(3, 
						new TreeNode(6), new TreeNode(7)
				)
			);
	}
	
	public static void main(String[] args) {
		_100_Same_Tree obj = new _100_Same_Tree();
		LogUtils.println("结果", 
				obj.isSameTree(
				obj.newTree1(),
				obj.newTree2()
				));
	}
}
